#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
void InsertSort(int* a, int n)
{
	for(int i=0;i<n-1;i++)
	{
		int end = i;
		int tmp = a[end+1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end+1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = end + gap;
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end] = a[end + gap];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end +gap] = tmp;
		}
	}
}

void Swap(int *p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}

void SelectSort1(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int start = i;
		int min = start;
		while (start <n)
		{
			if (a[start] < a[min])
			{
				min = start;
			}
			start++;
		}
		Swap(&a[i], &a[min]);
	}
}

void SelectSort2(int* a, int n)
{
	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int minIndex = left;
		int maxIndex = left;
		int i = 0;
		for (int i = left; i < right - 1; i++)
		{
			if (a[i] < a[minIndex])
				minIndex = i;
			if (a[i] > a[maxIndex])
				 maxIndex=i;
		}
		Swap(&a[minIndex], &a[left]);
		if (maxIndex == left)
		{
			maxIndex = minIndex;
		}
		Swap(&a[maxIndex], &a[right]);
		left++;
		right--;
	}
}








//void ShellSort(int* a, int n)
//{
//
//	int gap = n;
//	while (gap > 1)
//	{
//		gap /= 2;
//		int i = 0;
//		for (int i = 0; i < n - gap; i++)
//		{
//			int end = i;
//			int tmp = a[end + gap];
//			while (end >= 0)
//			{
//				if (a[end] > tmp)
//				{
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else
//				{
//					break;
//				}
//			}
//			a[end + gap] = tmp;
//		}
//	}
//}